|
In computer science, SLR grammars are the class of formal grammars accepted by a Simple LR parser. SLR grammars are a superset of all LR(0) grammars and a subset of all LALR(1) and LR(1) grammars. When processed by an SLR parser, an SLR grammar is converted into parse tables with no shift/reduce or reduce/reduce conflicts for any combination of LR(0) parser state and expected lookahead symbol. If the grammar is not SLR, the parse tables will have shift/reduce conflicts or reduce/reduce conflicts for some state and some lookahead symbols, and the resulting rejected parser is no longer deterministic. The parser cannot decide whether to shift or reduce next, or cannot decide between two candidate reductions. SLR parsers use a Follow(A) calculation to pick the lookahead symbols to expect for every completed nonterminal. LALR parsers use a different calculation which sometimes gives smaller, tighter lookahead sets for the same parser states. Those smaller sets can eliminate overlap with the state's shift actions, and overlap with lookaheads for other reductions in this same state. The overlap conflicts reported by SLR parsers are then spurious, a result of the approximate calculation using Follow(A). A grammar which is ambiguous will have unavoidable shift/reduce conflicts or reduce/reduce conflicts for every LR analysis method, including SLR. A common way for computer language grammars to be ambiguous is if some nonterminal is both left- and right-recursive: ::Expr → Expr * Val ::Expr → Val + Expr ::Expr → Val == Definitions == A rule of the form ''B → y •'' within a state of a SLR(1) automaton is said to be irreducible or in a ''reduced state'' because it has been completely expanded and is incapable of undergoing any shift transition. Rules in this state will have a dot ( • , the current look-ahead position) located at the rightmost end of its RHS (Right Hand Side). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「SLR grammar」の詳細全文を読む スポンサード リンク
|